home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d18 / tprolog.arc / SORTS.PRO < prev   
Text File  |  1991-08-03  |  3KB  |  74 lines
  1.  
  2. /************************************************************************
  3.  *                                                                      *
  4.  *  These are the insertion sort, bubble sort, and quick sort algos     *
  5.  *  from C&M implemented for Turbo Prolog.  The functions are only      *
  6.  *  defined here for lists of symbols, but can handle other list types  *
  7.  *  by adding to the predicate declarations.                            *
  8.  *                                                                      *
  9.  *  Compiled by John Reece                                              *
  10.  *                                                                      *
  11.  ************************************************************************/
  12.  
  13. domains
  14.    list = symbol*
  15.   
  16. predicates
  17.    append(list,list,list)         /* Needed by bubble sort and quick sort */
  18.    order(symbol,symbol)           /* Succeeds if the first and second parameters are 
  19.                                      are in the desired order - here in ascending order  */
  20.    insertsort(list,list)          /* Insertion sort */
  21.    insortx(symbol,list,list)      /* Needed by insertion sort */
  22.    bubblesort(list,list)          /* Bubble sort */
  23.    quicksort(list,list)           /* Quick sort */
  24.    split(symbol,list,list,list)   /* Needed by quick sort */
  25.  
  26. clauses
  27.  
  28. /***** used by bubblesort() and quicksort() *****/
  29.  
  30. append([],L,L).
  31. append([H|T],L,[H|V]) if
  32.       append(T,L,V).
  33.  
  34. /****** order(A,B) succeeds if the predicates are in the desired order.  This is
  35.         not necessarily a trivial definition in comparing certain domain types.  ******/
  36.       
  37. order(A,B) if
  38.    A < B.
  39.  
  40. /****** The insertion sort method, what else? ******/ 
  41.    
  42. insertsort([],[]).
  43. insertsort([X|L],M) if
  44.       insertsort(L,N) and
  45.       insortx(X,N,M).
  46. insortx(X,[A|L],[A|M]) if
  47.       order(A,X) and
  48.       ! and
  49.       insortx(X,L,M).
  50. insortx(X,L,[X|L]).
  51.  
  52. /***** bubble sort method *****/
  53.  
  54. bubblesort(L,S) if
  55.       append(X,[A,B|Y],L) and
  56.       
  57.       order(B,A) and
  58.       append(X,[B,A|Y],M) and
  59.       bubblesort(M,S) and
  60.       !.
  61. bubblesort(L,L).
  62.       
  63. /***** the quick sort method - the best if the list is totally out of order *****/
  64.  
  65. quicksort([],[]).
  66. quicksort([H|T],S) if
  67.        split(H,T,A,B) and
  68.        quicksort(A,A1) and
  69.        quicksort(B,B1) and
  70.        append(A1,[H|B1],S).
  71. split(H,[A|X],[A|Y],Z) if A <= H and split(H,X,Y,Z).
  72. split(H,[A|X],Y,[A|Z]) if A > H and split(H,X,Y,Z).
  73. split(_,[],[],[]).
  74.